#include <vector>
using namespace std;

// 归并排序的思想是分而治之，将数组平均分为两个部分，分别排序后进行归并
void mergeSort(vector<int>& nums, int l, int r)
{
    if(l >= r) return ; 
    int mid = l + (r - l) / 2;
    // 对左右子数组分别排序
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
    vector<int> tmp(r - l + 1);
    int cur1 = l, cur2 = mid + 1, i = 0;
    while(cur1 <= mid && cur2 <= r) // 合并两个有序数组，用临时数组保存
    {
        tmp[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
    }
    // 处理前面没处理完的部分
    while(cur1 <= mid) tmp[i++] = nums[cur1++];
    while(cur2 <= r) tmp[i++] = nums[cur2++];
    // 用临时数组覆盖原始数组
    for(int j = l; j <= r; j++)
    {
        nums[j] = tmp[j - l]; 
    }
}